package T41_T50;

import datastructure.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class T48 {
    /*思路：使用前缀和（和T10类似）
    * 1.用哈希表记录前缀和出现次数
    * 2.寻找targetSum子数组和，只需要遍历哈希表，找x=map[j]-targetSum在map中的出现次数*/
    int res=0;
    Map<Long,Integer> map=new HashMap<>();
    public int pathSum(TreeNode root,int targetSum){
        map.put(0L,1);
        dfs(root,targetSum,0);
        return res;
    }
    /**记录前缀和出现次数并写入res
     * @param node
     * @param targetSum
     * @param s root到node前缀和
     */
    private void dfs(TreeNode node,int targetSum,long s){
        if (node==null)return;
        s+=node.val;
        res+=map.getOrDefault(s-targetSum,0);
        //合并，将前缀和的出现次数加到map中
        map.merge(s,1,Integer::sum);
        dfs(node.left,targetSum,s);
        dfs(node.right,targetSum,s);
        map.merge(s,-1,Integer::sum); //删除左子树前缀和信息
    }
}
